Problem statement: zenit16ckc
Celé kopy sladkostí
Počet bodov: 40, časový limit: 2000ms
V predošlých kolách ste mali tú česť spoznať Bonifáca, Kleofáša a Hortenziu, vášnivých milovníkov sladkostí. Bonifác aj Hortenzia už mali možnosť vybrať si cukríky. Takže teraz je rad na Kleofášovi. Vybral sa i ten za podivným pánom v kabáte a ten mu, ako už jeho kamarátom predtým, ponúkol na výber z kôp cukríkov. Kleofášovi sa ale nechce vyberať tri najväčšie kopy tak, aby boli deliteľné troma. Radšej by si zobral nejaké tri kopy a šiel rýchlo späť. Nechce ale, aby sa mu Hortenzia smiala. Keď však prinesie viac cukríkov ako Bonifác, iste sa mu nebude smiať…
Chcel by teda vedieť, koľko je takých rôznych trojíc kôp cukríkov, že ich súčet je väčší ako ten, čo priniesol Bonifác. Ak je ich dostatočne veľa, nemusí krvopotne preberať všetky rôzne trojice, ale s dobrou šancou mu stačí zhrabnúť náhodnú trojicu so súčtom deliteľným tromi. A hádate správne, opäť je na vás, aby ste to spočítali.
Úloha
Zistite, koľko rôznych trojíc kôp môže Kleofáš vybrať tak, aby bol súčet cukríkov na týchto kopách väčší ako ten, ktorý priniesol Bonifác. Súčet cukríkov z týchto troch kôp musí byť deliteľný tromi.
Vstup a výstup
Na prvom riadku sú čísla \(1 \leq n \leq 1500\) a \(1 \leq s \leq 3\,000\,000\): počet kôp cukríkov a počet cukríkov, ktoré Bonifác priniesol. Samozrejme, Bonifác doniesol počet cukríkov deliteľný tromi. V druhom riadku je \(n\) medzerou oddelených čísel \(1 \leq c_i \leq 10^6\): počet cukríkov na jednotlivých kopách.
Na jediný riadok výstupu vypíšte jedno číslo: počet trojíc rôznych kôp cukríkov, ktoré mohol Kleofáš vybrať tak, aby súčet cukríkov na nich bol deliteľný tromi, a pritom bol väčší ako \(s\).
Trojice kôp cukríkov považujeme za rôzne, ak aspoň jedna kopa cukríkov je v jednej trojici, ale nie v druhej.
Dajte si pozor na veľkosti premenných.
Príklad
Input:
6 12
6 4 2 7 3 5Output:
4(6,4,5), (6,2,7), (6,7,5), (7,3,5)
